package leetcodev1.字符串;

import leetcodev1.链表.Solution;

import java.util.ArrayList;
import java.util.List;

public class LeetCode22 {
    //可以基于中间状态搞事情的都可以考虑动态规划
    //这道题有中间状态，但是最终结果不是要n种，而是要具体的排列组合
    //1.枚举  1 <= n <= 8
    //2.递归枚举出来
    public List<String> generateParenthesis(int n) {
        List<String> ret = new ArrayList<>();
        dfs(ret, n, 0, 0, "");
        return ret;
    }

    //使用了string的final
    //浪费空间可以使用StringBuilder进行回溯
    private void dfs(List<String> ret, int n, int leftCount, int rightCount, String route) {
        if (leftCount == n && rightCount == n) {
            ret.add(route);
            return;
        }

        //加左括号
        if (leftCount < n) {
            dfs(ret, n, leftCount + 1, rightCount, route + "(");
        }

        //加右括号
        if (leftCount > rightCount) {
            dfs(ret, n, leftCount, rightCount + 1, route + ")");
        }
    }
}

class Answer22{
    //方法1 枚举所有情况再依次检查(不写了..)
    //方法2 回溯法 比直接递归节约了空间 刚才那个不知道为啥不行..
    public List<String> generateParenthesis(int n) {
        List<String> ans = new ArrayList<String>();
        backtrack(ans, new StringBuilder(), 0, 0, n);
        return ans;
    }

    public void backtrack(List<String> ans, StringBuilder cur, int open, int close, int max) {
        if (cur.length() == max * 2) {
            ans.add(cur.toString());
            return;
        }
        if (open < max) {
            cur.append('(');
            backtrack(ans, cur, open + 1, close, max);
            cur.deleteCharAt(cur.length() - 1);
        }
        if (close < open) {
            cur.append(')');
            backtrack(ans, cur, open, close + 1, max);
            cur.deleteCharAt(cur.length() - 1);
        }
    }

    ArrayList[] cache = new ArrayList[100];//利用缓存 减少计算量 空间换时间

    public List<String> generate(int n) {
        if (cache[n] != null) {
            return cache[n];
        }
        ArrayList<String> ans = new ArrayList<String>();
        if (n == 0) {
            ans.add("");
        } else {
            //有多少对括号
            for (int c = 0; c < n; ++c) {
                for (String left: generate(c)) {//遍历左括号集合
                    for (String right: generate(n - 1 - c)) {//遍历有括号集合
                        ans.add("(" + left + ")" + right);
                    }
                }
            }
        }
        cache[n] = ans;
        return ans;
    }

    public List<String> generateParenthesis2(int n) {
        //返回n个括号的结果集合
        return generate(n);
    }

    public static void main(String[] args) {
        Answer22 answer22=new Answer22();
        answer22.generateParenthesis2(4);
    }
}
